/**
 * Copyright (c) 2009 Koder Chen. All Rights Reserved.
 *
 * tst_helper.c
 *
 * The file defines the functions using to help the test of the rsa lib
 *
 *  Author: chenfuhan
 * Created: 2009-6-24
 * Version: 1.0
 */
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

#include "tst_helper.h"

void int2bytes(u32_t a, u8_pt out)
{
	i32_t i = 0;
	while(a > 0)
	{
		out[i] = a & 0xff;
		a = (a >> 8);
		++i;
	}
}

u32_t bytes2int(u8_pt a)
{
	return (a[3] << 24) + (a[2] << 16) + (a[1] << 8) + a[0];
}

u32_t intbits(u32_t a)
{
	i32_t r = 31;
	while(r >=  0)
	{
		if((a >> r) & 1)
		{
			return r + 1;
		}
		r = r - 1;
	}
	return 0;
}

u32_t gcd(u32_t p, u32_t q)
{
    if (p<q) return gcd(q, p);
    if (q == 0) return p;
    return gcd(q, p%q);
}

u32_t powm(u32_t a, u32_t p, u32_t n)
{
	u32_t result = a % n;
	i32_t t = 31;
	while(!((p >> t) & 1) && t >= 0)
	{
		t -- ;
	}
	t = t - 1;
	while(t >= 0)
	{
		if((p >> t) & 1)
		{
			result = ((a % n) * ((result * result) % n)) % n;
		}
		else
		{
			result = (result * result) % n;
		}
		t --;
	}
	return result;
}

i32_t jacobi(i32_t a, i32_t b)
{
	if (a % b == 0)
	{
		return 0;
	}
	i32_t result = 1, t = 0;
	while (a > 1)
	{
		if (a & 1)
		{
			if ((((a-1) * (b-1)) >> 2) & 1)
			{
				result = -result;
			}
			t = b;
			b = a;
			a = t % a;
		}
		else
		{
			if (((b * b - 1) >> 3) & 1)
			{
				result = -result;
			}
			a = (a >> 1);
		}
	}
	return result;
}

i32_t jacobi_witness(i32_t x, i32_t n)
{
	i32_t j = jacobi(x, n) % n;
	i32_t f = powm(x, (n-1)/2, n);
	
	if(j == f) return 0;
	return 1;
}

i32_t randomize_prime_test(i32_t n, i32_t k)
{
	i32_t i = 0, x = 0;
	for(i = 0; i<=k;i++)
	{
		x = rsa_rand() % (n-1) + 1;
		if (jacobi_witness(x, n))
		{
			return 0;
		}
	}
	return 1;
}
